一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是完美二叉树。对于深度为 D 的,有 N 个结点的二叉树,若其结点对应于相同深度完美二叉树的层序遍历的前 N 个结点,这样的树就是完全二叉树。
给定一棵完全二叉树的后序遍历,请你给出这棵树的层序遍历结果。
输入格式:
输入在第一行中给出正整数 N(≤30),即树中结点个数。第二行给出后序遍历序列,为 N 个不超过 100 的正整数。同一行中所有数字都以空格分隔。
输出格式:
在一行中输出该树的层序遍历序列。所有数字都以 1 个空格分隔,行首尾不得有多余空格。
输入样例:
1 2
| 8 91 71 2 34 10 15 55 18
|
输出样例:
思路
由于题目中给定了这是一个完全二叉树,所以根据题目中给出后序遍历的序列建出树,左儿子下标为 2 * i, 右儿子下标为 2 * i + 1, 然后再按顺序输出即可。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| #include<bits/stdc++.h> using namespace std; const int maxn = 110; typedef struct node { int l = 0,r = 0; int data; }Node; Node T[maxn]; int n; void postorder(int i) { if(T[i].l) postorder(T[i].l); if(T[i].r) postorder(T[i].r); cin >> T[i].data; } int main() { cin >> n; for(int i=1;i<=n;i++){ if(i * 2 <= n) T[i].l = i * 2; if((i * 2 + 1) <= n) T[i].r = i * 2 + 1; } postorder(1); for(int i=1;i<=n;i++){ if(i != 1) cout << " "; cout << T[i].data; } return 0; }
|